package ink.lovejinhu.acwing.baseAl;

/**
 * @author jinhu
 * created 2021-05-11 20:41
 */
public class QuickSort {
//    public static void main(String[] args) {
//        int i = 0;
//        int j = 0;
//        int t = 0;
//        System.out.println(++i);
//        System.out.println(j++);
//
//        System.out.println(t++ + 7);
//
//
//    }

    /**
     * 快速排序思想，随机选取一个值，让左边的都小于这个值，右边的都大于这个值
     * 1.随机选取一个分界点
     * 2.让这个分界点左边的都小于这个数，右边的都大于这个数
     * 3.递归左右
     *
     * @param nums
     */
    public void quick(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = left - 1;
        int j = right + 1;
        //   int mid = nums[(left + right) >> 1];
        int mid = nums[left + right >> 1];    //选取分界点
        while (i < j) {     //让这个分界点左边的都都小于这个数，让这个分界点右边的都大于这个数
            do {
                i++;
            } while (nums[i] < mid);
            do {
                j--;
            } while (nums[j] > mid);
            if (i < j) swap(nums, i, j);  //在这里num[i]==num[]j,要么就num[i]>num[j],就是因为这里导致他们相等会交换位置，导致快排不稳定
        }
        quick(nums, left, i - 1);     //递归左边
        quick(nums, j + 1, right);         //递归右边
    }

    //闫总快排模板 v.v
    public static void quickSort(int[] q, int l, int r) {
        if (l >= r) return;
        int x = q[l + r >> 1];

        //Define positions of two pointers
        int i = l - 1;
        int j = r + 1;

        while (i < j) {
            do i++; while (q[i] < x);
            do j--; while (q[j] > x);
            //do Swap
            if (i < j) {
                int temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
        }

        quickSort(q, l, i - 1);
        quickSort(q, j + 1, r);
    }

    public void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }

    public int getRandomBetweenLeftAndRight(int left, int right) {
        double random = left + (right - left + 1) * Math.random();
        return (int) random;
    }

    //    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int i = scanner.nextInt();
//        int[] ints = new int[i];
//        for (int j = 0; j < i; j++) {
//            ints[j] = scanner.nextInt();
//        }
//        for (int j = 0; j < i; j++) {
//            System.out.print(ints[j]);
//        }
//        System.out.println();
//        QuickSort quickSort = new QuickSort();
//        quickSort.quick(ints, 0, ints.length - 1);
//        for (int j = 0; j < ints.length; j++) {
//            System.out.print(ints[j] + " ");
//        }
//    }
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] test = {1, 3, 2, 4, 5, 2, 1};
        quickSort.quick(test, 0, test.length - 1);
        for (int i = 0; i < test.length; i++) {
            System.out.print(test[i] + " ");

        }
        //  System.out.println(1+2>>1);

    }
}
